1. Field of the Invention
The present invention relates generally to a communication system using Low-Density Parity-Check (LDPC) codes, and in particular, to a channel encoding/decoding method and apparatus for generating LDPC codes having various codeword lengths and code rates from a given LDPC code.
2. Description of the Related Art
In wireless communication systems, the link performance significantly decreases due to various noises in channels, a fading phenomenon, and Inter-Symbol Interference (ISI). Therefore, in order to realize high-speed digital communication systems requiring high data throughput and reliability, such as the next-generation mobile communication, digital broadcasting, and portable internet, it is necessary to develop a technology for eliminating noise, fading, and ISI. Recently, an intensive study of an error-correcting code has been conducted as a method for increasing communication reliability by efficiently recovering distorted information.
An LDPC code, first introduced by Gallager in 1960s, has lost favor over time due to its implementation complexity which could not be resolved by the technology at that time. However, as the turbo code, which was discovered by Berrou, Glavieux, and Thitimajshima in 1993, shows the performance approximating Shannon's channel limit, research has been conducted on iterative decoding and channel encoding based on a graph along with analyses on performance and characteristic of the turbo code. Due to this research, the LDPC code was restudied in the late 1990s, and proved that LDPC code has performance approximating the Shannon's channel limit if it undergoes decoding by applying iterative decoding based on a sum-product algorithm on a Tanner graph (a special case of a factor graph) corresponding to the LDPC code.
The LDPC code is typically represented using a graph representation technique, and many characteristics can be analyzed through the methods based on graph theory, algebra, and probability theory. Generally, a graph model of channel codes is useful for description of codes, and by mapping information on encoded bits to vertexes in the graph and mapping relations between the bits to edges in the graph, it is possible to consider a communication network in which the vertexes exchange predetermined messages through the edges, thus making it possible to derive a natural decoding algorithm. For example, a decoding algorithm derived from a trellis, which can be regarded as a kind of graph, can include the well-known Viterbi algorithm and a Bahl, Cocke, Jelinek and Raviv (BCJR) algorithm.
The LDPC code is generally defined as a parity-check matrix, and can be represented using a bipartite graph, which is referred to as a Tanner graph. The bipartite graph means that vertexes constituting the graph are divided into two different types, and the LDPC code is represented with the bipartite graph composed of vertexes, some of which are called variable nodes and the other of which are called check nodes. The variable nodes are one-to-one mapped to the encoded bits.
With reference to FIGS. 1 and 2, a description will be made of a graph representation method for the LDPC code.
FIG. 1 shows an example of a parity-check matrix H1 of the LDPC code composed of 4 rows and 8 columns. Referring to FIG. 1, since the number of columns is 8, the parity-check matrix H1 means an LDPC code that generates a length-8 codeword, and the columns are mapped to 8 encoded bits.
FIG. 2 is a diagram illustrating a Tanner graph corresponding to H1 of FIG. 1.
Referring to FIG. 2, the Tanner graph of the LDPC code is composed of 8 variable nodes x1 (202), x2 (204), x3 (206), x4 (208), x5 (210), x6 (212), x7 (214) and x8 (216), and 4 check nodes 218, 220, 222 and 224. An ith column and a jth row in the parity-check matrix H1 of the LDPC code are mapped to a variable node xi and a jth check node, respectively. In addition, a value of 1, i.e., a non-zero value, at the point where an ith column and a jth row in the parity-check matrix H1 of the LDPC code cross each other, means that there is an edge between the variable node xi and the jth check node on the Tanner graph of FIG. 2.
In the Tanner graph of the LDPC code, a degree of the variable node and a check node means the number of edges connected to each respective node, and the degree is equal to the number of non-zero entries in a column or row corresponding to the associated node in the parity-check matrix of the LDPC code. For example, in FIG. 2, degrees of the variable nodes x1 (202), x2 (204), x3 (206), x4 (208), x5 (210), x6 (212), x7 (214) and x8 (216) are 4, 3, 3, 3, 2, 2, 2 and 2, respectively, and degrees of check nodes 218, 220, 222 and 224 are 6, 5, 5 and 5, respectively. In addition, the numbers of non-zero entries in the columns of the parity-check matrix H1 of FIG. 1, which correspond to the variable nodes of FIG. 2, are coincident with their degrees 4, 3, 3, 3, 2, 2, 2 and 2, and the numbers of non-zero entries in the rows of the parity-check matrix H1 of FIG. 1, which correspond to the check nodes of FIG. 2, are coincident with their degrees 6, 5, 5 and 5.
In order to represent degree distribution for the nodes of the LDPC code, a ratio of the number of degree-i variable nodes to the total number of variable nodes is defined as fi, and a ratio of the number of degree-j check nodes to the total number of check nodes is defined as gj. For example, for the LDPC code corresponding to FIGS. 1 and 2, f2= 4/8, f3=⅜, f4=⅛, and fi=0 for i≠2, 3, 4; and g5=¾, g6=¼, and gj=0 for j≠5, 6. When a length of the LDPC code is defined as N, i.e., the number of columns is defined as N, and when the number of rows is defined as N/2, the density of non-zero entries in the entire parity-check matrix having the above degree distribution is computed as Equation (1).
                                                        2              ⁢                              f                2                            ⁢              N                        +                          3              ⁢                              f                3                            ⁢              N                        +                          4              ⁢                              f                4                            ⁢              N                                            N            ·                          N              /              2                                      =                  5.25          N                                    (        1        )            
In Equation (1), as N increases, the density of ‘1’s in the parity-check matrix decreases. Generally, as for the LDPC code, since the code length N is inversely proportional to the density of non-zero entries, the LDPC code with a large N has a very low density. The wording ‘low-density’ in the name of the LDPC code originates from the above-mentioned relationship.
Next, with reference to FIG. 3, a description will be made of characteristics of a parity-check matrix of a structured LDPC code to be applied in the present invention. FIG. 3 schematically illustrates an LDPC code adopted as the standard technology in DVB-S2, which is one of the European digital broadcasting standards.
In FIG. 3, N1 denotes a length of an LDPC codeword, K1 provides a length of an information word, and (N1−K1) provides a parity length. Further, M1 and q are determined to satisfy q=(N1−K1)/M1. Preferably, K1/M1 should be an integer. For convenience, the parity-check matrix of FIG. 3 is called a first parity-check matrix H1.
Referring again to FIG. 3, a structure of a parity part, i.e., K1th column through (N1−1)th column, in the parity-check matrix, has a dual diagonal shape. Therefore, as for degree distribution over columns corresponding to the parity part, all columns have a degree ‘2’, except for the last column having a degree ‘1’.
In the parity-check matrix, a structure of an information part, i.e., 0th column through (K1−1)th column, is made using the following rules.
Rule 1: It generates a total of K1/M1 column groups by grouping K1 columns corresponding to the information word in the parity-check matrix into multiple groups of M1 columns. A method for forming columns belonging to each column group follows Rule 2 below.
Rule 2: It first determines positions of ‘1’s in each 0th column in ith column groups (where i=1, . . . , K1/M1). When a degree of a 0th column in each ith column group is denoted by Di, if positions of rows with 1 are assumed to be Ri,0(1), Ri,0(2), . . . , Ri,0(Di), positions Ri,j(k)(k=1,2, . . . , Di) of rows with 1 are defined as Equation (2), in a jth column (where j=1,2, . . . , M1−1) in an ith column group.Ri,j(k)=Ri,(j−1)(k)+q mod(N1−K1),k=1,2, . . . , Di, i=1, . . . , K1/M1, j=1, . . . , M1−1   (2)
According to the above rules, it is can be appreciated that degrees of columns belonging to an ith column group are all equal to Di. For a better understanding of a structure of a DVB-S2 LDPC code that stores information on the parity-check matrix according to the above rules, the following detailed example will be described.
As a detailed example, for N1=30, K1=15, M1=6 and q=3, three sequences for the information on the position of rows with 1 (hereafter, these sequences are called “Weight-1 Position Sequences” for convenience' sake) for 0th columns in 3 column groups can be expressed as;R1,0(1)=0, R1,0(2)=1, R1,0(3)=2,R2,0(1)=0, R2,0(2)=11, R2,0(3)=13,R3,0(1)=0, R3,0(2)=10, R3,0(3)=14.
Regarding the weight-1 position sequence for 0th columns in each column group, only the corresponding position sequences can be expressed as follows for each column group, for convenience' sake. For example:                0 1 2        0 11 13        0 10 14.        
In other words, the ith weight-1 position sequence in the ith line sequentially represents the information on the position of rows with 1 for the column group.
It is possible to generate an LDPC code having the same concept as that of a DVB-S2 LDPC code of FIG. 4, by forming a parity-check matrix using the information corresponding to the detailed example, and Rule 1 and Rule 2.
It is known that the DVB-S2 LDPC code designed in accordance with Rule 1 and Rule 2 can be efficiently encoded using the structural shape. A process of performing LDPC encoding using the DVB-S2 based parity-check matrix will be described below by way of example.
In the following exemplary description, as a detailed example, a DVB-S2 LDPC code with N1=16200, K1=10800, M1=360 and q=15 undergoes an encoding process. For convenience, information bits having a length K1 are represented as (i0, i1, . . . , iK1−1), and parity bits having a length (N1−K1) are expressed as (p0, p1, . . . , pN1−K1−1).
Step 1: An encoder initializes parity bits as follows:p0=p1=. . . =pN1−K1−1=0
Step 2: The encoder reads information on a row where 1 is located within the first column group of an information word, from the 0th weight-1 position sequence of the stored sequences indicating the parity-check matrix.                0 2084 1613 1548 1286 1460 3196 4297 2481 3369 3451 4620 2622R1,0(1)=0, R1,0(2)=2048, R1,0(3)=1613, R1,0(4)=1548, R1,0(5)=1286,R1,0(6)=1460, R1,0(7)=3196, R1,0(8)=4297, R1,0(9)=2481, R1,0(10)=3369,R1,0(11)=3451, R1,0(12)=4620, R1,0(13)=2622.        
The encoder updates particular parity bits px in accordance with Equation (3) using the read information and the first information bit i0. Herein, x means a value of R1,0(k) for k=1,2, . . . , 13.p0=p0⊕i0, p2064=p2064⊕i0, p1613=p1613⊕i0,p1548=p1548⊕i0, p1286=p1286⊕i0, p1460=p1460⊕i0,p3196=p3196⊕i0, p4297=p4297⊕i0, p2481=p2481⊕i0,p3369=p3369⊕i0, p3451=p3451⊕i0, p4620=p4620⊕i0,p2622=p2622⊕i0   (3)
In Equation (3), px=px⊕i0 can also be expressed as px←px⊕i0, and ⊕ means binary addition.
Step 3: The encoder first finds out a value of Equation (4) for the next 359 information bits im (where m=1,2, . . . , 359) after i0.{x+(m mod M1)×q} mod (N1−K1), M1=360, m=1,2, . . . , 359   (4)
In Equation (4), x means a value of R1,0(k) for k=1,2, . . . , 13. It should be noted that Equation (4) has the same concept as Equation (2).
Next, the encoder performs an operation similar to Equation (3) using the value found in Equation (4). That is, the encoder updates p{x+(m mod M1)×q} mod(N1−K1) for im. For example, for m=1, i.e., for i1, the encoder updates parity bits p(x+q)mod(N1−K1) as defined in Equation (5).p15=p15⊕i1, p2099=p2099⊕i1, p1628=p1628⊕i1,p1563=p1563⊕i1, p1301=p1301⊕i1, p1475=p1475⊕i1,p3211=p3211⊕i1, p4312=p4312⊕i1, p2496=p2496⊕i1,p3384=p3384⊕i1, p3466=p3466⊕i1, p4635=p4635⊕i1,p2637=p2637⊕i1   (5)
It should be noted that q=15 in Equation (5). The encoder performs the above process for m=1, 2, . . . , 359, in the same manner as shown above.
Step 4: As in Step 2, the encoder reads information of R2,0(K)(k=1, 2, . . . , 13), the 1st weight-1 position sequence, for a 361st information bit i360, and updates particular px, where x means R2,0(k). The encoder updates P{x+(m mod M1)×q} mod(N1−K1), m=361,362, . . . , 719 by similarly applying Equation (4) to the next 359 information bits i361, i362, . . . , i719 after i360.
Step 5: The encoder repeats Steps 2, 3 and 4 for all groups each having 360 information bits.
Step 6: The encoder finally determines parity bits using Equation (6).pi=pi⊕pi−1, i=1,2, . . . , N1−K1−1   (6)
The parity bits pi of Equation (6) are parity bits that underwent LDPC encoding.
As described above, DVB-S2 performs encoding through the process of Step 1 through Step 6.
In order to apply the LDPC code to the actual communication system, the LDPC code should be designed to be suitable for the data rate required in the communication system. Particularly, not only in an adaptive communication system employing a Hybrid Automatic Retransmission Request (HARQ) scheme and an Adaptive Modulation and Coding (AMC) scheme, but also in a communication system supporting various broadcast services, LDPC codes having various codeword lengths are needed to support various data rates according to the system requirements.
However, as described above, the LDPC code used in the DVB-S2 system has only two types of codeword lengths due to its limited use, and each type of the LDPC code needs an independent parity-check matrix. For these reasons, there is a long-felt need in the art for a method for supporting various codeword lengths to increase extendibility and flexibility of the system. Particularly, in the DVB-S2 system, transmission of data comprising several hundreds to thousands of bits is needed for transmission of signaling information. However, since only 16200 and 64800 are available for a length of the DVB-S2 LDPC code, it is necessary to support various codeword lengths.
In addition, since storing independent parity-check matrix separately for each codeword length of the LDPC code reduces the overall memory efficiency, there is a demand for a scheme capable of efficiently supporting various codeword lengths from the given existing parity-check matrix, without designing a new parity-check matrix.